Technologies for the control of unmanned ground vehicles (UGVs) attempting to perform local path navigation while traversing unknown, off-road terrains permit simple longer-range path planning, such as navigation between human-specified waypoints. However, these technologies have yet to develop automated plan generation strategies toward achieving higher-level mission goals (e.g., reconnaissance, surveillance, and target acquisition) in light of changing environmental conditions, evolving mission requirements, and a desire or need to coordinate movement of multiple vehicles.
Approaches that have been used to address path planning and routing have included traditional artificial intelligence (AI) algorithms. For example, classical planning, hierarchical-task-network planning, and case-based planning use symbolic planning based on logic and reasoning. However, the problem of interest is essentially numeric, and hence less suited for reasoning about goals and sub-goals. Although AI planning techniques may be applied to a higher-level strategic planning problem—i.e., how to decide what the mission goals are—their utility is diminished in the context of tactical planning problems wherein the mission goals are already known.
Other approaches, such as coordinated robot planning, focus on collision avoidance as a primary criterion for path planning. In many contexts, there is so much space compared to the number of vehicles that the probability of collision is slim. Yet other multi-robot planning algorithms are primarily concerned with formations and moving of vehicles in unison, and not on balanced workload distribution. Investigations into coordinating robot behavior by dividing the workload have generally been reactive (local) rather than deliberative (global), losing the benefits of planning ahead for multiple goals. Furthermore, when assigning goals, path planning is treated as a separate problem, thus substantially ignoring an enemy or obstacle between a vehicle/robot and a nearby goal point.
One investigation into controlling UGVs is the Distributed Architecture for Mobile Navigation (DAMN), carried out at Carnegie Mellon University. DAMN includes behaviors such as “road following,” “seeking the next navigation goal,” “obstacle avoidance,” and “avoid hazards.” Each behavior provides a vote on the next direction to take. A command arbiter decides upon the best direction, which is then acted upon by the UGV. DAMN also includes a global navigator to determine a full path to a goal position. However, DAMN uses a D* (dynamic A*) search algorithm. This approach, however, does not accommodate as many criteria and as much information, at the deliberative planning level, that are generally at play, when determining mission assignments and paths that are not fooled by local gradients.